package middle;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import util.PrintUtils;

public class Solution_57 {
    public int[][] insert(int[][] intervals, int[] newInterval) {
        int leftIndex = -1, rightIndex = intervals.length;
        while (true) {

        }
    }
    public int[][] insert2(int[][] intervals, int[] newInterval) {
        int leftIndex = -1, rightIndex = intervals.length;
        for (int i = 0; i < intervals.length; i++) {
            if (newInterval[0] < intervals[i][0]) {
                break;
            } else if (intervals[i][0] <= newInterval[0] && newInterval[0] <= intervals[i][1]) {
                leftIndex = i;
                break;
            } else {
                leftIndex = i + 1;
            }
        }
        for (int i = intervals.length - 1; i >= 0; i--) {
            if (newInterval[1] > intervals[i][1]) {
                break;
            } else if (intervals[i][0] <= newInterval[1] && newInterval[1] <= intervals[i][1]) {
                rightIndex = i;
                break;
            } else {
                rightIndex = i - 1;
            }
        }
        List<int[]> list = new ArrayList<>();
        if (leftIndex == -1 && rightIndex == intervals.length) {
            list.add(newInterval);
        } else if (leftIndex == -1 && rightIndex == -1) {
            list.add(newInterval);
            list.addAll(Arrays.asList(intervals));
        } else if (leftIndex == intervals.length && rightIndex == intervals.length) {
            list.addAll(Arrays.asList(intervals));
            list.add(newInterval);
        } else {
            for (int i = 0; i < leftIndex; i++) {
                list.add(intervals[i]);
            }
            if (leftIndex <= rightIndex) {
                int min = leftIndex == -1 ? newInterval[0] : Math.min(intervals[leftIndex][0], newInterval[0]);
                int max = rightIndex == intervals.length ? newInterval[1] : Math.max(intervals[rightIndex][1], newInterval[1]);
                list.add(new int[]{min, max});
            }/* else if (leftIndex == rightIndex) {
                list.add(new int[]{Math.min(intervals[leftIndex][0], newInterval[0]), Math.max(intervals[rightIndex][1], newInterval[1])});
            }*/ else {
                list.add(newInterval);
            }
            for (int i = rightIndex + 1; i < intervals.length; i++) {
                list.add(intervals[i]);
            }
        }
        return list.toArray(new int[0][2]);
    }

    public static void main(String[] args) {
        Solution_57 model = new Solution_57();
//        int[][] ints = model.insert(new int[][]{{1, 3}, {6, 9}}, new int[]{2, 5});
//        int[][] ints = model.insert(new int[][]{{1, 3}, {6, 9}}, new int[]{4, 7});
        int[][] ints = model.insert(new int[][]{{1, 3}, {6, 9}}, new int[]{4, 5});
//        int[][] ints = model.insert(new int[][]{{1, 3}, {6, 9}}, new int[]{-1, 0});
//        int[][] ints = model.insert(new int[][]{{1, 3}, {6, 9}}, new int[]{10, 11});
//        int[][] ints = model.insert(new int[][]{{1, 3}, {6, 9}}, new int[]{-1, 11});
//        int[][] ints = model.insert(new int[][]{}, new int[]{10, 11});
//        int[][] ints = model.insert(new int[][]{{1, 5}}, new int[]{2, 7});
//        int[][] ints = model.insert(new int[][]{{1, 5}}, new int[]{-1, 2});
//        int[][] ints = model.insert(new int[][]{{0, 5}, {9, 12}}, new int[]{7, 16});
        for (int[] anInt : ints) {
            PrintUtils.arrayInt(anInt);
        }
    }
}
